package org.xiaoxin.leetcode.array;

import java.util.*;

/**
 * 560. 和为 K 的子数组
 * <p>
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * <p>
 * 子数组是数组中元素的连续非空序列。
 * <p>
 * 示例 1：
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * <p>
 * 示例 2：
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 * <p>
 * 提示：
 * 1 <= nums.length <= 2 * 10^4
 * -1000 <= nums[i] <= 1000
 * -10^7 <= k <= 10^7
 * <p>
 * 难度：中等
 * 标签：数组、哈希表、前缀和
 *
 * @author xiaoxin
 */
public class _560_SubarraySumEqualsK {

    /**
     * 方法一：暴力解法
     * 思路：枚举所有子数组，计算其和，判断是否等于k
     * 时间复杂度：O(n^2)，其中 n 是数组的长度
     * 空间复杂度：O(1)
     */
    public int subarraySum1(int[] nums, int k) {
        // 提示：
        // 1. 使用两层循环枚举所有子数组
        // 2. 计算子数组的和，判断是否等于k
        int length = nums.length;
        int count = 0;
        for (int i = 0; i < length; i++) {
            int sum = 0;
            for (int j = i; j < length; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 方法二：前缀和 + 哈希表
     * 思路：使用哈希表记录前缀和的出现次数，优化时间复杂度
     * 时间复杂度：O(n)，其中 n 是数组的长度
     * 空间复杂度：O(n)，哈希表在最坏情况下可能有 n 个不同的键值
     */
    public int subarraySum2(int[] nums, int k) {
        // 提示：
        // 1. 使用哈希表记录前缀和的出现次数
        // 2. 遍历数组，计算当前前缀和，在哈希表中查找 (当前前缀和 - k) 出现的次数
        // 3. 更新哈希表中当前前缀和的出现次数
        int count = 0;
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        int prefixSum = 0;
        prefixSumCount.put(0, 1);
        for (int num : nums) {
            prefixSum += num;
            count += prefixSumCount.getOrDefault(prefixSum - k, 0);
            prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        testAllMethods();
    }

    /**
     * 测试所有方法
     */
    private static void testAllMethods() {
        System.out.println("=== 560. 和为 K 的子数组 - 测试用例 ===\n");

        // 示例 1
        int[] nums1 = {1, 1, 1};
        int k1 = 2;
        testCase("示例 1", nums1, k1, 2);

        // 示例 2
        int[] nums2 = {1, 2, 3};
        int k2 = 3;
        testCase("示例 2", nums2, k2, 2);

        // 额外测试用例

        // 测试用例 3：包含负数
        int[] nums3 = {1, -1, 0};
        int k3 = 0;
        testCase("测试用例 3（包含负数）", nums3, k3, 3);

        // 测试用例 4：较大数组
        int[] nums4 = {3, 4, 7, 2, -3, 1, 4, 2};
        int k4 = 7;
        testCase("测试用例 4（较大数组）", nums4, k4, 4);

        // 测试用例 5：全部元素相同
        int[] nums5 = {3, 3, 3, 3, 3};
        int k5 = 3;
        testCase("测试用例 5（全部元素相同）", nums5, k5, 5);

        // 测试用例 6：k为0
        int[] nums6 = {-1, -1, 1, 1, 0};
        int k6 = 0;
        testCase("测试用例 6（k为0）", nums6, k6, 4);
    }

    /**
     * 测试单个用例
     */
    private static void testCase(String testName, int[] nums, int k, int expected) {
        System.out.println(testName + ":");
        System.out.println("输入: nums = " + Arrays.toString(nums) + ", k = " + k);
        System.out.println("期望结果: " + expected);

        _560_SubarraySumEqualsK solution = new _560_SubarraySumEqualsK();

        // 测试方法一
        int result1 = solution.subarraySum1(nums, k);
        boolean method1Correct = result1 == expected;
        System.out.println("方法一结果: " + result1 + " " +
                (method1Correct ? "✅" : "❌"));

        // 测试方法二
        int result2 = solution.subarraySum2(nums, k);
        boolean method2Correct = result2 == expected;
        System.out.println("方法二结果: " + result2 + " " +
                (method2Correct ? "✅" : "❌"));

        boolean allCorrect = method1Correct && method2Correct;
        System.out.println("整体测试: " + (allCorrect ? "✅ 通过" : "❌ 失败"));
        System.out.println();
    }
}